import collections
from typing import List


class Solution:
    def maxGroupNumber(self, tiles: List[int]) -> int:
        count = collections.Counter(tiles)
        nums = sorted(count.keys())

        ans = 0
        now = []
        for i in range(len(nums)):
            if now:
                if nums[i] > nums[i - 1] + 1:  # 不连续的情况
                    ans += self.count_continuation(now)
                    now = []
            now.append(count[nums[i]])
        ans += self.count_continuation(now)
        return ans

    def count_continuation(self, nums):
        """连续数列计算：count=每一个数字的频数"""
        print("连续数列:", nums)

        # 连续数列不足3个数的情况：只需要考虑刻子
        if len(nums) < 3:
            return sum(num // 3 for num in nums)

        ans = 0

        # 连续数列大于等于3个的情况：每一步结合前2个，考虑尽可能在得出最多组的结果下，保留最多的牌（优先最后一个，然后优先倒数第二个）
        for i in range(2, len(nums)):
            max_shun = min(nums[i - 2], nums[i - 1], nums[i])  # 最大顺子数

            if max_shun == 0:
                ans += nums[i - 2] // 3
                nums[i - 2] %= 3

            else:
                choose = []
                for j in range(max_shun, max(max_shun - 3, 0), -1):  # 遍历所有的不同顺子数提取选择
                    res = j + (nums[i - 2] - j) // 3 + (nums[i - 1] - j) // 3 + (nums[i] - j) // 3
                    left1 = (nums[i - 1] - j) % 3
                    left2 = (nums[i] - j) % 3
                    choose.append([res, left2, left1, j])
                choose.sort(reverse=True)
                print(choose)
                res, left2, left1, j = choose[0]

                ans += j
                nums[i - 2] -= j
                nums[i - 1] -= j
                nums[i] -= j
                ans += nums[i - 2] // 3
                nums[i - 2] %= 3

            print(ans, max_shun, nums)

        ans += nums[-2] // 3 + nums[-1] // 3

        print("连续数列结果:", ans)

        return ans


if __name__ == "__main__":
    print(Solution().maxGroupNumber([2, 2, 2, 3, 4]))  # 1
    print(Solution().maxGroupNumber([2, 2, 2, 3, 4, 1, 3]))  # 2

    # 测试用例22/72 : 13
    print(Solution().maxGroupNumber(
        [1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 10, 10, 10,
         10, 11, 11, 11, 12]))
